package flp.solvers.genetic;
import flp.solvers.*;
import flp.Layout;
import flp.Usage;
import flp.exceptions.FlowImpossibleException;
import flp.exceptions.LayoutBuildException;
import flp.problem.ProblemInstance;
import java.util.Random;

/**
 * Klasa szukajaca rozwiazania FLP przy uzyciu algorytmu genetycznego.
 * 
 * @author Ania i Necro
 */
public class GeneticSolver extends Solver 
{
    static {
        preferableCostFunction = Layout.CostFunction.DAGSP;
    }
    
    private GeneticSettings currentSettings;
    
    /**
     * Konstruktor klasy GeneticSolver.
     * 
     * @param currentProblem ProblemInstance ktory Solver rozwiazuje.
     * @param currentSettings Ustawienia z jakimi Solver pracuje.
     * @param optMon Klasa monitorujaca postep ewolucji.
     */
    public GeneticSolver(ProblemInstance currentProblem, GeneticSettings currentSettings,
            IOptimizationMonitor optMon) {
        super(currentProblem, optMon);
        this.currentSettings = currentSettings;
    }
    /** 
     * Metoda przeprowadzająca obliczenia optymalizacyjne.
     * Korzysta z podanych w konstruktorze ustawien.
     * 
     * @return Najlepsze znalezione rozwiazanie.
     */
    @Override
    public Layout computeSolution() throws LayoutBuildException, FlowImpossibleException
    {
        try {
            Population currentPopulation = Population.generatePopulation(currentSettings,toSolve);
            if(currentSettings.getType() == 0) 
                performEvolutionRouletteMethod(currentPopulation,optMonitor);
            else 
                performImprovedEvolution(currentPopulation, optMonitor);

            Layout result = currentPopulation.getTop();
            result.getCost(Layout.CostFunction.DAGSP);
            return result;       
            
       } catch (LayoutBuildException lbe){
           // metoda zwraca null, ktory handler interpretuje jako rzucenie
           // wyjatku "LayoutBuildException"
           return null;
       }
        
    }
        

    /**
     * Metoda przeprowadzajaca mutacje.
     * 
     * @author Ania
     * @param input Layout poddawany mutacji.
     */
    private static void mutate(Layout input,int mutPossibility){
        Random rand = new Random();
        boolean found = false;
        int a = rand.nextInt(mutPossibility);
        //pos1, pos2 - numery pozycji do zamiany
        int pos1, pos2;
        Usage tmp;
        if(a == 1){
                                                       
        int iterFlag = 1000;                                              
            while(!found && (iterFlag > 0)){
                pos1 = rand.nextInt(input.getSize());
                pos2 = rand.nextInt(input.getSize());
                tmp = input.getPlace(pos1);
                input.setPlace(pos1, input.getPlace(pos2));
                input.setPlace(pos2, tmp);
                if(input.checkCorrectness())
                    found = true;
                else{                           //cofniecie mutacji
                    tmp = input.getPlace(pos1);
                    input.setPlace(pos1, input.getPlace(pos2));
                    input.setPlace(pos2, tmp);
                    
                    iterFlag--;
                }
            }
        }
    }
    
    /**
     * Metoda przeprowadzająca krzyzowanie dwoch layoutow: lay1, lay2 
     * stosujac point-to-point crossover.
     * 
     * @author Ania
     * @return Najlepszy layout z tych bedacych wynikiem krzyzowania.
     */
    Layout crossOver(Layout lay1, Layout lay2, int mutPossibility)
            throws FlowImpossibleException
    {
            /**Referencja wskazujaca dziecko o aktualnie najnizszym koszcie.*/
            Layout best = null;           
            Layout copy1 = lay1.clone();
            Layout copy2 = lay2.clone(); 
          
            Usage tmp;

            for(int i = 0; i<copy1.getSize()-1; i++){              
                    tmp = copy1.getPlace(i);
                    copy1.setPlace(i, copy2.getPlace(i));
                    copy2.setPlace(i, tmp);
                    //System.out.println("child1:" + copy1);
                    if(copy1.checkCorrectness()){
                        copy1.getCost(preferableCostFunction);
                        if( best == null  || ( best.getCost(preferableCostFunction) > copy1.getCost(preferableCostFunction)) )
                            best = copy1.clone();
                    }
                    //System.out.println("child2:" + copy2);
                    if(copy2.checkCorrectness()){
                        copy2.getCost(preferableCostFunction);
                        if( best == null ) { 
                            best = copy2.clone();
                        }else if ( best.checkCorrectness() && best.getCost(preferableCostFunction) > copy2.getCost(preferableCostFunction))
                            best = copy2.clone();
                    }	
            }
            //System.out.println("best child:" + best);
            
            if (best != null){
                if (best.checkCorrectness()) {
                    GeneticSolver.mutate(best,mutPossibility);
                    best.getCost(preferableCostFunction);
                    return best;
                } else return null;
            } 
            return null;
    }
    
    /** 
     * Metoda reprezentujaca proces ewolucji danej populacji. 
     * Wersja podsawowa, najprostsza.
     * 
     * @param population Populacja ewoluujaca.
     * @param monitor Progress-monitor dla procesu.
     */
    public void performEvolution(Population population, IOptimizationMonitor monitor)
            throws FlowImpossibleException
    {
      Random rand = new Random();            
            int stopIt=0; //licznik kroków dla których spełniony jest warunek stopu
            
            //@debug zmienna do statystyk
            int cost_same = 0;
            
            int newcost=population.getTotalCost();
            int oldcost;
            //pętla główna, for ogranicza ilość kroków do MaxIterations
            
            
            int topcost=population.getTop().getCost(preferableCostFunction);
            monitor.markProgress("TOP AT START: "+topcost+
                                "\nSUM AT START: "+population.getTotalCost());
                                
            for(int iter=0 ; iter<this.getCurrentSettings().getMaxIterations() ; iter++){
                
                //@todo uzgodnić informacje jakie przyjmuje monitor
                if (iter%10==0)    
                    monitor.markProgress("STEP:"+iter+"   SUM:"+newcost+"   TOP:"+
                            population.getTop().getCost(preferableCostFunction)+"   SC:"+stopIt);
                    
                
                
                //nowy koszt populacji w poprzednim kroku staje się starym kosztem w kroku obecnym
                oldcost=newcost;
                
                Object[] lay_arr = population.getSpeciments().toArray(); //tworzenie ze zbioru tablicy layoutów
                
                Layout fresh = null; //Zmienna przechowywująca najlepszy z nowych layoutów
                
                //Póki nie zostanie wygenerowany poprawny potomek powtarzaj cross-over
                while(fresh == null){
       
                    //losowanie layoutów do krzyżowania
                    int id1 = rand.nextInt(lay_arr.length);
                    int id2 = rand.nextInt(lay_arr.length);
                    
                    //System.out.println("ID1:"+id1+"  ID2:"+id2);
                    Layout lay1 = (Layout) lay_arr[id1];
                    
                    Layout lay2 = (Layout) lay_arr[id2];
                    
                    //crossover
                    fresh = this.crossOver(lay1,lay2,this.getCurrentSettings().getMutationProbability());
                }
                               
                //Zamiana z najgorszym layoutem populacji starej, pod warunkiem, że nie zdegraduje to populacji
                newcost+= population.swapWorst(fresh);
                        
                //******************************************************************
                //@debug, zmodyfikowane do zebrania danych statystycznych
                  
                  if(topcost == population.getTop().getCost(preferableCostFunction)){
                      cost_same++;
                  } else {
                      cost_same=0;
                      topcost=population.getTop().getCost(preferableCostFunction);
                  }
                   
                  
                  if(iter==this.getCurrentSettings().getMaxIterations()-1 ||
                          stopIt==this.getCurrentSettings().getStopIterations()-1){
                  
                  monitor.markProgress("STEPS: "+iter+
                                "\nSTOP COND ITERS: "+stopIt+
                                "\nSUM AT END: "+newcost+
                                "\nTOP AT END: "+population.getTop().getCost(preferableCostFunction)+
                                "\nTOP_SINCE: "+(iter-cost_same));
                
                  }
                  
                /* UWAGA !!! Warunek stopu liczę jako różnicę kosztem sumarycznym populacji
                 nowej, i kosztem sumarycznym populacji starej */
                
                //jeżeli spełniony jest warunek stopu
                if (population.checkStopCondition(newcost , oldcost,this)){
                    //zwiększamy licznik
                    stopIt++;
                    
                    //i sprawdzamy czy osiągnął on żądaną wartość
                    if(stopIt >= this.getCurrentSettings().getStopIterations()){
                        //koniec iteracji jeżeli licznik osiągnął żądaną wartość
                        
                        return;
                    }
                } else {
                    
                    //w przeciwnym wypadku zerujemy licznik
                    stopIt=0;
                }
                
                
               
            } //pętla główna  
            
    }
    
    
    /**
     * Metoda przeprowadzajaca ewolucje korzystajaca z metody ruletki.
     * W wyborze Layoutow do krzyzowania z wiekszym prawdopdoobienstwem
     * decyduje sie na te, ktorych koszt jest lepszy.
     * 
     * @param population Populacja, ktorej optymalizacja jest przeprowadzana.
     * @param monitor Progress-monitor dla procesu.
     */
    public void performEvolutionRouletteMethod(Population population, IOptimizationMonitor monitor)
            throws FlowImpossibleException, LayoutBuildException
    {   
      
            int stopIt=0; //licznik kroków dla których spełniony jest warunek stopu
            
            //@debug zmienna do statystyk
            int cost_same = 0;
            
            int newcost=population.getTotalCost();
            int oldcost;
            //pętla główna, for ogranicza ilość kroków do MaxIterations
            
            
            int topcost=population.getTop().getCost(preferableCostFunction);
            monitor.markProgress("TOP AT START: "+topcost+
                                "\nSUM AT START: "+population.getTotalCost());
                                
            for(int iter=0 ; iter<this.getCurrentSettings().getMaxIterations() ; iter++){
                if (stoppedFlag){
                    return;
                }
                //WYSYŁANIE DANYCH DO MONITORA
                //@todo sprzątnąć pierwszy markProgress po zakonczeniu testów
                monitor.markProgress("STEP:"+iter+"   SUM:"+newcost+"   TOP:"+
                        population.getTop().getCost(preferableCostFunction)+"   SC:"+stopIt);
                Object[] monValues = {iter, population.getTop().getCost(preferableCostFunction), newcost/population.getSize() , stopIt };
                monitor.markProgress(monValues);
                    
                
                
                //nowy koszt populacji w poprzednim kroku staje się starym kosztem w kroku obecnym
                oldcost=newcost;
                
                Layout fresh = null; //Zmienna przechowywująca najlepszy z nowych layoutów
                
                //Póki nie zostanie wygenerowany poprawny potomek powtarzaj cross-over
                while(fresh == null){
                    
                    //wybrane layouty do krzyżowania
                    Layout[] crossLayouts = population.getRandomSpeciments(100);
                    if(crossLayouts[0] == null) throw new LayoutBuildException("Zly wynik getRandomSpeciments()");
                    //crossover
                    fresh = this.crossOver(crossLayouts[0],crossLayouts[1],this.getCurrentSettings().getMutationProbability());
                }
                               
                //Zamiana z najgorszym layoutem populacji starej, pod warunkiem, że nie zdegraduje to populacji
                newcost+= population.swapWorst(fresh);
                        
                //******************************************************************
                //@debug, zmodyfikowane do zebrania danych statystycznych
                /*
                if(topcost == population.getTop().getCost(preferableCostFunction)){
                    cost_same++;
                } else {
                    cost_same=0;
                    topcost=population.getTop().getCost(preferableCostFunction);
                }
                */ 
                  
                  if(iter==this.getCurrentSettings().getMaxIterations()-1 ||
                          stopIt==this.getCurrentSettings().getStopIterations()-1){
                  }
                  
                /* Warunek stopu liczę jako różnicę kosztem sumarycznym populacji
                 nowej, i kosztem sumarycznym populacji starej */
                
                //jeżeli spełniony jest warunek stopu
                if (population.checkStopCondition(newcost , oldcost,this)){
                    //zwiększamy licznik
                    stopIt++;
                    
                    //i sprawdzamy czy osiągnął on żądaną wartość
                    if(stopIt >= this.getCurrentSettings().getStopIterations()){
                        //koniec iteracji jeżeli licznik osiągnął żądaną wartość
                        
                        return;
                    }
                } else {
                    
                    //w przeciwnym wypadku zerujemy licznik
                    stopIt=0;
                }
            } //pętla główna      
    }
    
    /**
     * Jeszcze jedna metoda implememntujaca przeprowadzanie ewolucji.
     * Tym razem odbywa się ona w wyraznych krokach a konkretne pokolenia sa oddzielone
     * oprocz cross-over i mutacji wprowadzamy takze wymieranie slabych osobnikow.
     * Dobor osobnikow do reprodukcji odbywa sie podobnie jak w RouletteMethod.
     * 
     * @param population Populacja, ktorej optymalizacja jest przeprowadzana.
     * @param monitor Progress-monitor dla procesu.
     */
    public void performImprovedEvolution(Population population, IOptimizationMonitor monitor) 
            throws LayoutBuildException, FlowImpossibleException
    {

            Random rand = new Random();
            
            //@todo ustawienia - wrzucic do settings 
            //@DONE
            //final int MAX_OUTER_ITERATIONS = 10;
            
            //petla zewnetrzna - jeden obieg to stworzenie nowej generacji
            int outerLoopIter = 0;
            int oldCost = population.getTotalCost();
            int newCost = 0;
            //warrunek stopy - roznica kosztow dwoch kolejnych populacji mniejsza od epsilona, lub przekroczono MAX_ITER
            while ( outerLoopIter++ < currentSettings.getRedrawCount() /*&& oldCost - newCost > currentSettings.getEpsilon() */)  {
                
                // 1. Cross-overy
                int innerLoopIter = 0; 
                int populationSize = 100;
                int stopIt=0; //licznik kroków dla których spełniony jest warunek stopu
            
                int newcost=population.getTotalCost();
                int oldcost;
                
                int stopMe = 0;  
                for(int iter=0 ; iter<this.getCurrentSettings().getMaxIterations() ; iter++){
                      if (stoppedFlag){
                          return;
                      }
                      //System.out.println("POPULATION: "+outerLoopIter + "   STEP:"+iter+"   SUM:"+newcost+"   TOP:"+
                      //      population.getTop().getCost(preferableCostFunction)+"   SC:"+stopMe+ "   COUNT" + population.getSize() );
                    
                      //nowy koszt populacji w poprzednim kroku staje się starym kosztem w kroku obecnym
                      oldcost=newcost;
                      Layout fresh = null; 
                      while(fresh == null)  {                                              //powtarzaj cross-over do poprawnego potomka
                             Layout[] crossLayouts = population.getRandomSpeciments();//population.getRandomSpeciments(100);     //wybrane layouty do krzyżowania
                             fresh = this.crossOver(crossLayouts[0],crossLayouts[1],this.getCurrentSettings().getMutationProbability());
                      }
                               
                     //Zamiana z najgorszym layoutem populacji starej, pod warunkiem, że nie zdegraduje to populacji
                     int add = population.swapWorst(fresh);
                     if(add < 0) {
                        newcost+= add;
                        stopMe = 0;
                     } else {
                         stopMe++;
                     }
                       

                     if(iter==this.getCurrentSettings().getMaxIterations()-1 ||
                            stopIt==this.getCurrentSettings().getStopIterations()-1){
                  
                     monitor.markProgress("STEPS: "+iter+
                                "\nSUM AT END: "+newcost+
                                "\nTOP AT END: "+population.getTop().getCost(preferableCostFunction));             
                    }
                     Object[] monValues = {iter, population.getTop().getCost(preferableCostFunction), newcost/population.getSize(), stopIt, outerLoopIter};
                     monitor.markProgress(monValues);
                     //tu warunek stopu dla tej petli - jezeli od 100 iteracji nic nie ulepszylismy to wylazimy
                     if(stopMe > currentSettings.getStopIterations()) break;
                     
                    } //pętla inner loop - koniec
                
                    //2. dolosowanie osobnikow na miejsca tych ktorzy nie przezyja - bloodbath
                    int poorLayoutsToKill = 70; //zabijamy najgorsze 40% Layoutow
                    population.swapPoorLayouts( poorLayoutsToKill /*currentSettings.getPoorLayoutsToSwap()*/ ,toSolve, outerLoopIter );
          
                    //zliczenie sumarycznego kosztu
                    newCost = population.getTotalCost(); 
            }
    }    
    
    public GeneticSettings getCurrentSettings() {
        return currentSettings;
    }
}
